/**
 * 散列模块
 * License: BSD
 * Author: Bob Jenkins
 * Modifier: Lucifer(786325481@QQ.com)
 * Date: 11-8-2007
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.Hash;

import system.Traits;
version(unittest)
{
	import system.runtime.c.stdio;
}

//version = VALGRIND;
//debug = hash;

/**
 * 通用散列函数
 * Params: obj = 要散列的对象
 * Returns: 一个 32bit 大小的数字
 * Comments: 如果需要其他散列算法的函数，可以使用自由函数实现；
 *           如果在类/结构内实现 toHash() 函数，该泛型函数也可以调用。
 */
hash_t toHash(T)(T obj)
{
    //指针类型
    static if( IsPointerType!(T) )
    {
        static assert(false, "Type " ~ T.stringof ~ " is not supported.");
    }
    //结构类型
    else static if( is( T == struct ) )
    {
        static assert( is( typeof( T.toHash ) == function), "Struct " ~ T.stringof ~ " should implement toHash() function.");
        return obj.toHash();
    }
    //类类型
    else static if( is( T == class ) )
    {
        assert( obj !is null );
        return obj.toHash();
    }
    //接口类型
    else static if( is( T == interface ) )
    {
        Interface* pi = **cast(Interface ***)cast(void*)obj;
        Object o = cast(Object)(cast(void*)obj - pi.offset);
        assert( o !is null );
        return o.toHash();
    }
    //字符串和数组类型
    else static if( IsSomeString!(T) || IsArray!(T) )   //这里把字符串跟数组区分开，实际上这里可以只用IsArray!(T)
    {
        return .getHash!(T)(obj);
    }
    //整型类型
    else static if( is( T == byte ) )
    {
        return ( obj ^ ( obj << 8 ) );
    }
    else static if( is( T == ubyte ) )
    {
        return obj;
    }
    else static if( is( T == short ) )
    {
        return ( ( cast(ushort)obj ) | ( obj << 16 ) );
    }
    else static if( is( T == ushort ) )
    {
        return obj;
    }
    else static if( is( T == int ) )
    {
        return obj;
    }
    else static if( is( T == uint ) )
    {
        return obj;
    }
    else static if( is( T == long ) )
    {
        return ( ( cast(int)obj ) ^ ( cast(int)( obj >> 32 ) ) );
    }
    else static if( is( T == ulong ) )
    {
        return ( ( cast(int)obj ) ^ ( cast(int)( obj >> 32 ) ) );
    }
    //字符类型
    else static if( is( T == char ) )
    {
        return cast(ubyte)obj;
    }
    else static if( is( T == wchar ) )
    {
        return cast(ushort)obj;
    }
    else static if( is( T == dchar ) )
    {
        return (cast(uint)obj);
    }
    //实数和虚数类型
    else static if( is( T == float ) || is( T == ifloat ) )
    {
        auto f = obj;
        if( f == 0 )    //确保 +0.0 和 -0.0 所获得散列值一样
            return 0;
        return *(cast(int*)&f);
    }
    else static if( is( T == double ) || is( T == idouble ) )
    {
        auto d = obj;
        if( d == 0 )
            return 0;
        long l = *( cast(long*)&d );
        return ( ( cast(int)l ) ^ ( cast(int)( l >> 32 ) ) );
    }
    else static if( is( T == real ) || is( T == ireal ) )
    {
        auto r = obj;
        if( r == 0 )
            return 0;
        return typeid(T).getHash(&r);
    }
    //复数类型
    else static if( is( T == cfloat ) || is( T == cdouble ) || is( T == creal) )
    {
        auto numeric = obj;
        if( numeric == 0 )
            return 0;
        return typeid(T).getHash(&numeric);
    }
    else
    {
        return typeid(T).getHash(&obj);
    }
}

unittest
{
    auto numeric1 = 0.0i;
    auto numeric2 = -0.0i;
    auto numeric3 = 0.0;
    auto numeric4 = -0.0;

    assert(toHash(numeric1) == toHash(numeric2));
    assert(toHash(numeric3) == toHash(numeric4));

    auto numeric5 = (0.0) + (0.0i);
    auto numeric6 = (0.0) + (-0.0i);
    auto numeric7 = (-0.0) + (0.0i);
    auto numeric8 = (-0.0) + (-0.0i);

    assert( numeric5 == 0 );
    assert( numeric6 == 0 );
    assert( numeric7 == 0 );
    assert( numeric8 == 0 );

    assert( toHash(numeric5) == toHash(numeric6) );
    assert( toHash(numeric7) == toHash(numeric8) );
    assert( toHash(numeric5) == toHash(numeric7) );
    assert( toHash(numeric6) == toHash(numeric8) );
    assert( toHash(numeric5) == 0 );
}

/** 字符串与数组散列函数 */
hash_t getHash(T)(T value)
{
    static assert( IsArray!(T), "Argument " ~ T.stringof ~ "is not a string type.");

    version(LittleEndian)
    {
        return cast(hash_t)(hashLittle(cast(void*)value.ptr, value.length));
    }
    else version(BigEndian)
    {
        return cast(hash_t)(hashBig(cast(void*)value.ptr, value.length));
    }
}

/* ---------------------------- 32 bit hash ---------------------------- */

/**
 * These are functions for producing 32-bit hashes for hash table lookup.
 * hashWord(), hashLittle(), hashBig(), mix(), and last()
 * are externally useful functions.

 * You probably want to use hashLittle().  hashLittle() and hashBig()
 * hash byte arrays.  hashLittle() is is faster than hashBig() on
 * little-endian machines.  Intel and AMD are little-endian machines.
 * On second thought, you probably want hashLittle(void* key, size_t length, uint* pc, uint* pb),
 * which is identical to hashLittle() except it returns two 32-bit hashes for the price of one.

 * Examples:
 * -----------------------------------------------------------------------------------------
 * If you want to find a hash of, say, exactly 7 integers, do
 * a = i1;  b = i2;  c = i3;
 * mix(a,b,c);
 * a += i4; b += i5; c += i6;
 * mix(a,b,c);
 * a += i7;
 * last(a,b,c);
 * then use c as the hash value.  If you have a variable length array of
 * 4-byte integers to hash, use hashWord().  If you have a byte array (like
 * a character string), use hashLittle().  If you have several byte arrays, or
 * a mix of things, see the comments above hashLittle().
 * ----------------------------------------------------------------------------------------

 * Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
 * then mix those integers.  This is fast (you can do a lot more thorough
 * mixing with 12*3 instructions on 3 integers than you can with 3 instructions
 * on 1 byte), but shoehorning those bytes into integers efficiently is messy.
 */

version(LittleEndian)
{
    const int HashLittleEndian = 1;
    const int HashBigEndian = 0;
}
else version(BigEndian)
{
    const int HashLittleEndian = 0;
    const int HashBigEndian = 1;
}
else
{
    const int HashLittleEndian = 0;
    const int HashBigEndian = 0;
}

uint hashSize(uint n)
{
    return cast(uint)1 << (n);
}

uint hashMask(uint n)
{
    return hashSize(n) - 1;
}

uint rotative(uint x, uint k)
{
    return (((x) << (k)) | ((x) >> (32 - (k))));
}

/**
 * mix three 32-bit values reversibly.

 * This is reversible, so any information in (a,b,c) before mix() is
 * still in (a,b,c) after mix().

 * If four pairs of (a,b,c) inputs are run through mix(), or through
 * mix() in reverse, there are at least 32 bits of the output that
 * are sometimes the same for one pair and different for another pair.
 * This was tested for:
 * pairs that differed by one bit, by two bits, in any combination
 * of top bits of (a,b,c), or in any combination of bottom bits of
 * (a,b,c).
 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 * is commonly produced by subtraction) look like a single 1-bit
 * difference.
 * the base values were pseudorandom, all zero but one bit set, or
 * all zero plus a counter that starts at zero.

 * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
 * satisfy this are
 *   4  6  8 16 19  4
 *   9 15  3 18 27 15
 *  14  9  3  7 17  3
 * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
 * for "differ" defined as + with a one-bit base and a two-bit delta.  I
 * used http://burtleburtle.net/bob/hash/avalanche.html to choose
 * the operations, constants, and arrangements of the variables.

 * This does not achieve avalanche.  There are input bits of (a,b,c)
 * that fail to affect some output bits of (a,b,c), especially of a.  The
 * most thoroughly mixed value is c, but it doesn't really even achieve
 * avalanche in c.

 * This allows some parallelism.  Read-after-writes are good at doubling
 * the number of bits affected, so the goal of mixing pulls in the opposite
 * direction as the goal of parallelism.  I did what I could.  Rotates
 * seem to cost as much as shifts on every machine I could lay my hands
 * on, and rotates are much kinder to the top and bottom bits, so I used
 * rotates.
 */

void mix(ref uint a, ref uint b, ref uint c)
{
    a -= c;  a ^= rotative(c, 4);  c += b;
    b -= a;  b ^= rotative(a, 6);  a += c;
    c -= b;  c ^= rotative(b, 8);  b += a;
    a -= c;  a ^= rotative(c,16);  c += b;
    b -= a;  b ^= rotative(a,19);  a += c;
    c -= b;  c ^= rotative(b, 4);  b += a;
}

/**
 * last mixing of 3 32-bit values (a,b,c) into c

 * Pairs of (a,b,c) values differing in only a few bits will usually
 * produce values of c that look totally different.  This was tested for
 * pairs that differed by one bit, by two bits, in any combination
 * of top bits of (a,b,c), or in any combination of bottom bits of
 * (a,b,c).
 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 * is commonly produced by subtraction) look like a single 1-bit
 * difference.
 * the base values were pseudorandom, all zero but one bit set, or
 * all zero plus a counter that starts at zero.

 * These constants passed:
 * 14 11 25 16 4 14 24
 * 12 14 25 16 4 14 24
 * and these came close:
 *   4  8 15 26 3 22 24
 * 10  8 15 26 3 22 24
 * 11  8 15 26 3 22 24
 */

void last(ref uint a, ref uint b, ref uint c)
{
    c ^= b; c -= rotative(b,14);
    a ^= c; a -= rotative(c,11);
    b ^= a; b -= rotative(a,25);
    c ^= b; c -= rotative(b,16);
    a ^= c; a -= rotative(c,4);
    b ^= a; b -= rotative(a,14);
    c ^= b; c -= rotative(b,24);
}

/**
  * This works on all machines.  To be useful, it requires
  * that the key be an array of uint's, and
  * that the length be the number of uint's in the key

  * The function hashWord() is identical to hashLittle() on little-endian
  * machines, and identical to hashBig() on big-endian machines,
  * except that the length has to be measured in uint rather than in
  * bytes.  hashLittle() is more complicated than hashWord() only because
  * hashLittle() has to dance around fitting the key bytes into registers.
  */

uint hashWord(uint* key, size_t length, uint initval = 0)
{
    uint a,b,c;
    //Set up the internal state
    a = b = c = 0xDEADBEEF + ((cast(uint)length) << 2) + initval;
    //Handle most of the key
    while(length > 3)
    {
        a += key[0];
        b += key[1];
        c += key[2];
        mix(a,b,c);
        length -= 3;
        key += 3;
    }
    //Handle the last 3 uint's
    switch(length)                     //All the case statements fall through
    {
        case 3 :
            c+=key[2];
        case 2 :
            b+=key[1];
        case 1 :
            a+=key[0];
            last(a,b,c);
        case 0:                         //case 0: nothing left to add
        default: break;
    }
    //Report the result
    return c;
}


/**
 * Same as hashWord(uint* key, size_t length, uint initval = 0), but take two seeds and return two
 * 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
 * both be initialized with seeds.  If you pass in (*pb)==0, the output
 * (*pc) will be the same as the return value from hashWord(uint* key, size_t length, uint initval = 0).
 */

/**
 * Params: key -> the key, an array of uint values;
 *               length -> the length of the key, in uint;
 *               pc -> IN: seed OUT: primary hash value;
 *               pb -> IN: more seed OUT: secondary hash value.
 */

void hashWord(uint* key, size_t length, uint* pc, uint* pb)
{
    uint a, b, c;
    //Set up the internal state
    a = b = c = 0xDEADBEEF + (cast(uint)(length << 2)) + *pc;
    c += *pb;

    //Handle most of the key
    while (length > 3)
    {
        a += key[0];
        b += key[1];
        c += key[2];
        mix(a,b,c);
        length -= 3;
        key += 3;
    }

    //Handle the last 3 uint's
    switch(length)                     //All the case statements fall through
    {
        case 3 :
            c+=key[2];
        case 2 :
            b+=key[1];
        case 1 :
            a+=key[0];
            last(a,b,c);
        case 0:                             //case 0: nothing left to add
        default: break;
    }
    //Report the result
    *pc=c; *pb=b;
}

/**
 * hash a variable-length key into a 32-bit value
 * Params: k -> the key (the unaligned variable-length array of bytes)
 *               length -> the length of the key, counting by bytes
 *               initval -> can be any 4-byte value
 * Returns: a 32-bit value.
 * Comments: Every bit of the key affects every bit of
 *                     the return value.  Two keys differing by one or two bits will have
 *                     totally different hash values.

 * The best hash table sizes are powers of 2.  There is no need to do
 * mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 * use a bitmask.  For example, if you need only 10 bits, do
 * h = (h & hashmask(10));
 * In which case, the hash table should have hashsize(10) elements.

 * If you are hashing n strings (char**)k, do it like this:
 * for (i=0, h=0; i<n; ++i) h = hashLittle( k[i], len[i], h);

 * By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 * code any way you wish, private, educational, or commercial.  It's free.

 * Use for hash table lookup, or anything where one collision in 2^^32 is
 * acceptable.  Do NOT use for cryptographic purposes.
 */

uint hashLittle(void* key, size_t length, uint initval = 0)
{
    union U { void* ptr; size_t i; }                //needed for Mac Powerbook G4
    U u;
    uint a,b,c;                                             //internal state
    //Set up the internal state
    a = b = c = 0xDEADBEEF + (cast(uint)length) + initval;

    u.ptr = key;
    if (HashLittleEndian && ((u.i & 0x3) == 0))
    {
        uint* k = cast(uint*)key;         //read 32-bit chunks
        ubyte* k8;

        //all but last block: aligned reads and affect 32 bits of (a,b,c)
        while (length > 12)
        {
            a += k[0];
            b += k[1];
            c += k[2];
            mix(a,b,c);
            length -= 12;
            k += 3;
        }
        //handle the last (probably partial) block
        /*
         * "k[2] & 0xffffff" actually reads beyond the end of the string, but
         * then masks off the part it's not allowed to read.  Because the
         * string is aligned, the masked-off tail is in the same word as the
         * rest of the string.  Every machine with memory protection I've seen
         * does it on word boundaries, so is OK with this.  But VALGRIND will
         * still catch it and complain.  The masking trick does make the hash
         * noticably faster for short strings (like English words).
         */
         version(VALGRIND)
         {
            //make valgrind happy
            k8 = cast(ubyte *)k;
            switch(length)
            {
                case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
                case 11: c+=(cast(uint)k8[10]) << 16;                 //fall through
                case 10: c+=(cast(uint)k8[9]) << 8;                     //fall through
                case 9 : c+=k8[8];                                               //fall through
                case 8 : b+=k[1]; a+=k[0]; break;
                case 7 : b+=(cast(uint)k8[6]) << 16;                   //fall through
                case 6 : b+=(cast(uint)k8[5]) << 8;                     //fall through
                case 5 : b+=k8[4];                                               //fall through
                case 4 : a+=k[0]; break;
                case 3 : a+=(cast(uint)k8[2]) << 16;                   //fall through
                case 2 : a+=(cast(uint)k8[1]) << 8;                     //fall through
                case 1 : a+=k8[0]; break;
                case 0 : return c;
                default: break;
            }
         } //version(VALGRIND)
         else
         {
             switch(length)
            {
                case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
                case 11: c+=k[2] & 0xffffff; b+=k[1]; a+=k[0]; break;
                case 10: c+=k[2] & 0xffff; b+=k[1]; a+=k[0]; break;
                case 9 : c+=k[2] & 0xff; b+=k[1]; a+=k[0]; break;
                case 8 : b+=k[1]; a+=k[0]; break;
                case 7 : b+=k[1] & 0xffffff; a+=k[0]; break;
                case 6 : b+=k[1] & 0xffff; a+=k[0]; break;
                case 5 : b+=k[1] & 0xff; a+=k[0]; break;
                case 4 : a+=k[0]; break;
                case 3 : a+=k[0] & 0xffffff; break;
                case 2 : a+=k[0] & 0xffff; break;
                case 1 : a+=k[0] & 0xff; break;
                case 0 : return c;              //zero length strings require no mixing
                default: break;
            }
         }
    } //if (HashLittleEndian && ((u.i & 0x3) == 0))
    else if( HashLittleEndian && ((u.i & 0x1) == 0) )
    {
        ushort* k = cast(ushort*)key;   //read 16-bit chunks
        ubyte* k8;

        //all but last block: aligned reads and different mixing
        while (length > 12)
        {
            a += k[0] + ((cast(uint)k[1]) << 16);
            b += k[2] + ((cast(uint)k[3]) << 16);
            c += k[4] + ((cast(uint)k[5]) << 16);
            mix(a,b,c);
            length -= 12;
            k += 6;
        }

        //handle the last (probably partial) block
        k8 = cast(ubyte*)k;
        switch(length)
        {
            case 12:
                c+=k[4]+((cast(uint)k[5]) << 16);
                b+=k[2]+((cast(uint)k[3]) << 16);
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 11: c+=(cast(uint)k8[10]) << 16;     //fall through
            case 10:
                c+=k[4];
                b+=k[2]+((cast(uint)k[3]) << 16);
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 9 : c+=k8[8];                                  //fall through
            case 8 :
                b+=k[2]+((cast(uint)k[3]) << 16);
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 7 : b+=(cast(uint)k8[6]) << 16;            //fall through
            case 6 :
                b+=k[2];
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 5 : b+=k8[4];                                //fall through
            case 4 :
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 3 : a+=(cast(uint)k8[2]) << 16;      //fall through
            case 2 :
                a+=k[0];
                break;
            case 1 :
                a+=k8[0];
                break;
            case 0 : return c;                     //zero length requires no mixing
            default: break;
        }
    } //else if( HashLittleEndian && ((u.i & 0x1) == 0) )
    else
    {
        //need to read the key one byte at a time
        ubyte* k = cast(ubyte*)key;

        //all but the last block: affect some 32 bits of (a,b,c)
        while (length > 12)
        {
            a += k[0];
            a += (cast(uint)k[1]) << 8;
            a += (cast(uint)k[2]) << 16;
            a += (cast(uint)k[3]) << 24;
            b += k[4];
            b += (cast(uint)k[5]) << 8;
            b += (cast(uint)k[6]) << 16;
            b += (cast(uint)k[7]) << 24;
            c += k[8];
            c += (cast(uint)k[9]) << 8;
            c += (cast(uint)k[10]) << 16;
            c += (cast(uint)k[11]) << 24;
            mix(a,b,c);
            length -= 12;
            k += 12;
        }

        //last block: affect all 32 bits of (c)
        switch(length)                   //all the case statements fall through
        {
            case 12: c+=(cast(uint)k[11]) << 24;
            case 11: c+=(cast(uint)k[10]) << 16;
            case 10: c+=(cast(uint)k[9]) << 8;
            case 9 : c+=k[8];
            case 8 : b+=(cast(uint)k[7]) << 24;
            case 7 : b+=(cast(uint)k[6]) << 16;
            case 6 : b+=(cast(uint)k[5]) << 8;
            case 5 : b+=k[4];
            case 4 : a+=(cast(uint)k[3]) << 24;
            case 3 : a+=(cast(uint)k[2]) << 16;
            case 2 : a+=(cast(uint)k[1]) << 8;
            case 1 :
                a+=k[0];
                break;
            case 0 : return c;
            default: break;
        }
    } //else

    last(a,b,c);
    return c;
}

/**
 * Returns: two 32-bit hash values
 *
 * This is identical to hashLittle(void* key, size_t length, uint initval = 0), except it returns two 32-bit hash
 * values instead of just one.  This is good enough for hash table
 * lookup with 2^^64 buckets, or if you want a second hash if you're not
 * happy with the first, or if you want a probably-unique 64-bit ID for
 * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
 * a 64-bit value do something like "*pc + ((cast(ulong)*pb)<<32)".
 */

/**
 * Params: key -> the key to hash;
 *               length -> length of the key;
 *               pc -> IN: primary initval, OUT: primary hash;
 *               pb -> IN: secondary initval, OUT: secondary hash.
 */
void hashLittle(void* key, size_t length, uint* pc, uint* pb)
{
    union U { void* ptr; size_t i; }
    U u;                                            // needed for Mac Powerbook G4
    uint a, b, c;                                 // internal state
    //Set up the internal state
    a = b = c = 0xDEADBEEF + (cast(uint)length) + *pc;
    c += *pb;

    u.ptr = key;
    if(HashLittleEndian && ((u.i & 0x3) == 0))
    {
        uint* k = cast(uint*)key;    //read 32-bit chunks
        ubyte* k8;

        //all but last block: aligned reads and affect 32 bits of (a,b,c)
        while (length > 12)
        {
            a += k[0];
            b += k[1];
            c += k[2];
            mix(a,b,c);
            length -= 12;
            k += 3;
        }

        //handle the last (probably partial) block
        /*
         * "k[2] & 0xffffff" actually reads beyond the end of the string, but
         * then masks off the part it's not allowed to read.  Because the
         * string is aligned, the masked-off tail is in the same word as the
         * rest of the string.  Every machine with memory protection I've seen
         * does it on word boundaries, so is OK with this.  But VALGRIND will
         * still catch it and complain.  The masking trick does make the hash
         * noticably faster for short strings (like English words).
         */
         version(VALGRIND)
         {
             //make valgrind happy
             k8 = cast(const (ubyte*))k;
            switch(length)
            {
                case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
                case 11: c+=(cast(uint)k8[10]) << 16;                 //fall through
                case 10: c+=(cast(uint)k8[9]) << 8;                     //fall through
                case 9 : c+=k8[8];                                               //fall through
                case 8 : b+=k[1]; a+=k[0]; break;
                case 7 : b+=(cast(uint)k8[6]) << 16;                    //fall through
                case 6 : b+=(cast(uint)k8[5]) << 8;                      //fall through
                case 5 : b+=k8[4];                                                //fall through
                case 4 : a+=k[0]; break;
                case 3 : a+=(cast(uint)k8[2]) << 16;                     //fall through
                case 2 : a+=(cast(uint)k8[1]) << 8;                       //fall through
                case 1 : a+=k8[0]; break;
                case 0 : *pc=c; *pb=b; return;      //zero length strings require no mixing
                default: break;
            }
         } //version(VALGRIND)
         else
         {
             switch(length)
            {
                case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
                case 11: c+=k[2] & 0xffffff; b+=k[1]; a+=k[0]; break;
                case 10: c+=k[2] & 0xffff; b+=k[1]; a+=k[0]; break;
                case 9 : c+=k[2] & 0xff; b+=k[1]; a+=k[0]; break;
                case 8 : b+=k[1]; a+=k[0]; break;
                case 7 : b+=k[1] & 0xffffff; a+=k[0]; break;
                case 6 : b+=k[1] & 0xffff; a+=k[0]; break;
                case 5 : b+=k[1] & 0xff; a+=k[0]; break;
                case 4 : a+=k[0]; break;
                case 3 : a+=k[0] & 0xffffff; break;
                case 2 : a+=k[0] & 0xffff; break;
                case 1 : a+=k[0] & 0xff; break;
                case 0 : *pc=c; *pb=b; return;      //zero length strings require no mixing
                default: break;
            }
         }
    } //if(HashLittleEndian && ((u.i & 0x3) == 0))
    else if(HashLittleEndian && ((u.i & 0x1) == 0))
    {
        ushort* k = cast(ushort*)key;    //read 16-bit chunks
        ubyte* k8;

        //all but last block: aligned reads and different mixing
         while (length > 12)
        {
            a += k[0] + ((cast(uint)k[1]) << 16);
            b += k[2] + ((cast(uint)k[3]) << 16);
            c += k[4] + ((cast(uint)k[5]) << 16);
            mix(a,b,c);
            length -= 12;
            k += 6;
        }

        //handle the last (probably partial) block
        k8 = cast(ubyte*)k;
        switch(length)
        {
            case 12:
                c+=k[4]+((cast(uint)k[5]) << 16);
                b+=k[2]+((cast(uint)k[3]) << 16);
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 11: c+=(cast(uint)k8[10]) << 16;     //fall through
            case 10:
                c+=k[4];
                b+=k[2]+((cast(uint)k[3]) << 16);
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 9 : c+=k8[8];                                  //fall through
            case 8 :
                b+=k[2]+((cast(uint)k[3]) << 16);
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 7 : b+=(cast(uint)k8[6]) << 16;      //fall through
            case 6 :
                b+=k[2];
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 5 : b+=k8[4];                                  //fall through
            case 4 :
                a+=k[0]+((cast(uint)k[1]) << 16);
                break;
            case 3 : a+=(cast(uint)k8[2]) << 16;      //fall through
            case 2 :
                a+=k[0];
                break;
            case 1 :
                a+=k8[0];
                break;
            case 0 : *pc=c; *pb=b; return;      //zero length strings require no mixing
            default: break;
        }
    } //else if(HashLittleEndian && ((u.i & 0x1) == 0))
    else
    {
        // need to read the key one byte at a time

        ubyte* k = cast(ubyte*)key;

        //all but the last block: affect some 32 bits of (a,b,c)
        while (length > 12)
        {
            a += k[0];
            a += (cast(uint)k[1]) << 8;
            a += (cast(uint)k[2]) << 16;
            a += (cast(uint)k[3]) << 24;
            b += k[4];
            b += (cast(uint)k[5]) << 8;
            b += (cast(uint)k[6]) << 16;
            b += (cast(uint)k[7]) << 24;
            c += k[8];
            c += (cast(uint)k[9]) << 8;
            c += (cast(uint)k[10]) << 16;
            c += (cast(uint)k[11]) << 24;
            mix(a,b,c);
            length -= 12;
            k += 12;
        }

        //last block: affect all 32 bits of (c)
        switch(length)                                      //all the case statements fall through
        {
            case 12: c+=(cast(uint)k[11]) << 24;
            case 11: c+=(cast(uint)k[10]) << 16;
            case 10: c+=(cast(uint)k[9]) << 8;
            case 9 : c+=k[8];
            case 8 : b+=(cast(uint)k[7]) << 24;
            case 7 : b+=(cast(uint)k[6]) << 16;
            case 6 : b+=(cast(uint)k[5]) << 8;
            case 5 : b+=k[4];
            case 4 : a+=(cast(uint)k[3]) << 24;
            case 3 : a+=(cast(uint)k[2]) << 16;
            case 2 : a+=(cast(uint) k[1]) <<8;
            case 1 :
                a+=k[0];
                break;
            case 0 : *pc=c; *pb=b; return;      //zero length strings require no mixing
            default: break;
        }
    }

    last(a,b,c);
    *pc=c; *pb=b;
}

/**
 * This is the same as hashWord() on big-endian machines.  It is different
 * from hashLittle() on all machines.  hashBig() takes advantage of
 * big-endian byte ordering.
 */

uint hashBig(void* key, size_t length, uint initval = 0)
{
    union U{ void *ptr; size_t i; } // to cast key to (size_t) happily
    U u;
    uint a, b, c;

    //Set up the internal state
    a = b = c = 0xDEADBEEF + (cast(uint)length) + initval;

    u.ptr = key;
    if(HashBigEndian && ((u.i & 0x3) == 0))
    {
        uint* k = cast(uint*)key;    //read 32-bit chunks
        ubyte* k8;

        //all but last block: aligned reads and affect 32 bits of (a,b,c)
        while (length > 12)
        {
            a += k[0];
            b += k[1];
            c += k[2];
            mix(a,b,c);
            length -= 12;
            k += 3;
        }

        //handle the last (probably partial) block
        /*
         * "k[2] << 8" actually reads beyond the end of the string, but
         * then shifts out the part it's not allowed to read.  Because the
         * string is aligned, the illegal read is in the same word as the
         * rest of the string.  Every machine with memory protection I've seen
         * does it on word boundaries, so is OK with this.  But VALGRIND will
         * still catch it and complain.  The masking trick does make the hash
         * noticably faster for short strings (like English words).
         */
         version(VALGRIND)
         {
             //make valgrind happy
             k8 = cast(const (ubyte*))k;
            switch(length)
            {
                case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
                case 11: c+=(cast(uint)k8[10]) << 8;            //fall through
                case 10: c+=(cast(uint)k8[9]) << 16;            //fall through
                case 9 : c+=(cast(uint)k8[8]) << 24;             //fall through
                case 8 : b+=k[1]; a+=k[0]; break;
                case 7 : b+=(cast(uint)k8[6]) << 8;              //fall through
                case 6 : b+=(cast(uint)k8[5]) << 16;            //fall through
                case 5 : b+=(cast(uint)k8[4]) << 24;            //fall through
                case 4 : a+=k[0]; break;
                case 3 : a+=(cast(uint)k8[2]) << 8;              //fall through
                case 2 : a+=(cast(uint)k8[1]) << 16;            //fall through
                case 1 : a+=(cast(uint)k8[0]) << 24; break;
                case 0 : return c;
                default: break;
            }
         }//version(VALGRIND)
         else
         {
             switch(length)
            {
                case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
                case 11: c+=k[2] & 0xffffff00; b+=k[1]; a+=k[0]; break;
                case 10: c+=k[2] & 0xffff0000; b+=k[1]; a+=k[0]; break;
                case 9 : c+=k[2] & 0xff000000; b+=k[1]; a+=k[0]; break;
                case 8 : b+=k[1]; a+=k[0]; break;
                case 7 : b+=k[1] & 0xffffff00; a+=k[0]; break;
                case 6 : b+=k[1] & 0xffff0000; a+=k[0]; break;
                case 5 : b+=k[1] & 0xff000000; a+=k[0]; break;
                case 4 : a+=k[0]; break;
                case 3 : a+=k[0] & 0xffffff00; break;
                case 2 : a+=k[0] & 0xffff0000; break;
                case 1 : a+=k[0] & 0xff000000; break;
                case 0 : return c;                //zero length strings require no mixing
                default: break;
            }
         }
    }//if(HashBigEndian && ((u.i & 0x3) == 0))
    else
    {
        //need to read the key one byte at a time

        ubyte* k = cast(ubyte*)key;

        //all but the last block: affect some 32 bits of (a,b,c)
        while (length > 12)
        {
            a += (cast(uint)k[0]) << 24;
            a += (cast(uint)k[1]) << 16;
            a += (cast(uint)k[2]) << 8;
            a += (cast(uint)k[3]);
            b += (cast(uint)k[4]) << 24;
            b += (cast(uint)k[5]) << 16;
            b += (cast(uint)k[6]) << 8;
            b += (cast(uint)k[7]);
            c += (cast(uint)k[8]) << 24;
            c += (cast(uint)k[9]) << 16;
            c += (cast(uint)k[10]) << 8;
            c += (cast(uint)k[11]);
            mix(a,b,c);
            length -= 12;
            k += 12;
        }

        //last block: affect all 32 bits of (c)
        switch(length)                   //all the case statements fall through
        {
            case 12: c+=k[11];
            case 11: c+=(cast(uint)k[10]) << 8;
            case 10: c+=(cast(uint)k[9]) << 16;
            case 9 : c+=(cast(uint)k[8]) << 24;
            case 8 : b+=k[7];
            case 7 : b+=(cast(uint)k[6]) << 8;
            case 6 : b+=(cast(uint)k[5]) << 16;
            case 5 : b+=(cast(uint)k[4]) << 24;
            case 4 : a+=k[3];
            case 3 : a+=(cast(uint)k[2]) << 8;
            case 2 : a+=(cast(uint)k[1]) << 16;
            case 1 : a+=(cast(uint)k[0]) << 24;
                break;
            case 0 : return c;
            default: break;
        }
    }

    last(a,b,c);
    return c;
}

unittest
{
        //check that every input bit changes every output bit half the time
        const uint HashState = 1;
        const uint HashLen = 1;
        const uint MaxPair = 60;
        const uint MaxLen = 70;
        void driver2()
        {
            ubyte[MaxLen+1] qa;
            ubyte[MaxLen+2] qb;
            ubyte* a = &qa[0];
            ubyte* b = &qb[1];
            uint i=0, j=0, k, l, m=0, z;
            uint[HashState] c;
            uint[HashState] d;
            uint[HashState] e,f,g,h;
            uint[HashState] x,y;
            uint hlen;

            printf("No more than %d trials should ever be needed \n",MaxPair/2);
            for (hlen=0; hlen < MaxLen; ++hlen)
            {
                z=0;
                for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */
                {
                    for (j=0; j<8; ++j)   /*------------------------ for each input bit, */
                    {
                        for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
                        {
                            for (l=0; l<HashState; ++l)
                                e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~(cast(uint)0);

                            /*---- check that every output bit is affected by that input bit */
                            for (k=0; k<MaxPair; k+=2)
                            {
                                uint finished=1;
                                /* keys have one bit different */
                                for (l=0; l<hlen+1; ++l) {a[l] = b[l] = cast(ubyte)0;}
                                /* have a and b be two keys differing in only one bit */
                                a[i] ^= (k<<j);
                                a[i] ^= (k>>(8-j));
                                c[0] = hashLittle(a, hlen, m);
                                b[i] ^= ((k+1)<<j);
                                b[i] ^= ((k+1)>>(8-j));
                                d[0] = hashLittle(b, hlen, m);
                                /* check every bit is 1, 0, set, and not set at least once */
                                for (l=0; l<HashState; ++l)
                                {
                                    e[l] &= (c[l]^d[l]);
                                    f[l] &= ~(c[l]^d[l]);
                                    g[l] &= c[l];
                                    h[l] &= ~c[l];
                                    x[l] &= d[l];
                                    y[l] &= ~d[l];
                                    if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
                                }
                                if (finished) break;
                            }
                            if (k>z) z=k;
                            if (k==MaxPair)
                            {
                                printf("Some bit didn't change: ");
                                printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
                                        e[0],f[0],g[0],h[0],x[0],y[0]);
                                printf("i %d j %d m %d len %d\n", i, j, m, hlen);
                            }
                            if (z==MaxPair) goto done;
                        }
                    }
                }
                done:
                if (z < MaxPair)
                {
                    printf("Mix success  %2d bytes  %2d initvals  ",i,m);
                    printf("required  %d  trials\n", z/2);
                }
            }
            printf("\n");
        }

        //Check for reading beyond the end of the buffer and alignment problems
        void driver3()
        {
            ubyte[MaxLen+20] buf;
            ubyte* b;
            uint len;
            string q = "This is the time for all good men to come to the aid of their country..." ~ "\0";
            uint h;
            string qq = "xThis is the time for all good men to come to the aid of their country..." ~ "\0";
            uint i;
            string qqq = "xxThis is the time for all good men to come to the aid of their country..." ~ "\0";
            uint j;
            string qqqq = "xxxThis is the time for all good men to come to the aid of their country..." ~ "\0";
            uint refs,x,y;
            ubyte* p;

            printf("Endianness.  These lines should all be the same (for values filled in):\n");

            auto sizeofq = q.length;
            printf("%.8x                            %.8x                            %.8x\n",
            hashWord(cast(uint*)q, (sizeofq)/4, 13),
            hashWord(cast(uint*)q, (sizeofq-5)/4, 13),
            hashWord(cast(uint*)q, (sizeofq-9)/4, 13));
            p = cast(ubyte*)q.ptr;
            printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
            hashLittle(p, sizeofq-1, 13), hashLittle(p, sizeofq-2, 13),
            hashLittle(p, sizeofq + 1-3, 13), hashLittle(p, sizeofq-4, 13),
            hashLittle(p, sizeofq-5, 13), hashLittle(p, sizeofq-6, 13),
            hashLittle(p, sizeofq-7, 13), hashLittle(p, sizeofq-8, 13),
            hashLittle(p, sizeofq-9, 13), hashLittle(p, sizeofq-10, 13),
            hashLittle(p, sizeofq-11, 13), hashLittle(p, sizeofq-12, 13));
            p = cast(ubyte*)&qq[1];
            printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
            hashLittle(p, sizeofq-1, 13), hashLittle(p, sizeofq-2, 13),
            hashLittle(p, sizeofq-3, 13), hashLittle(p, sizeofq-4, 13),
            hashLittle(p, sizeofq-5, 13), hashLittle(p, sizeofq-6, 13),
            hashLittle(p, sizeofq-7, 13), hashLittle(p, sizeofq-8, 13),
            hashLittle(p, sizeofq-9, 13), hashLittle(p, sizeofq-10, 13),
            hashLittle(p, sizeofq-11, 13), hashLittle(p, sizeofq-12, 13));
            p = cast(ubyte*)&qqq[2];
            printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
            hashLittle(p, sizeofq-1, 13), hashLittle(p, sizeofq-2, 13),
            hashLittle(p, sizeofq-3, 13), hashLittle(p, sizeofq-4, 13),
            hashLittle(p, sizeofq-5, 13), hashLittle(p, sizeofq-6, 13),
            hashLittle(p, sizeofq-7, 13), hashLittle(p, sizeofq-8, 13),
            hashLittle(p, sizeofq-9, 13), hashLittle(p, sizeofq-10, 13),
            hashLittle(p, sizeofq-11, 13), hashLittle(p, sizeofq-12, 13));
            p = cast(ubyte*)&qqqq[3];
            printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
            hashLittle(p, sizeofq-1, 13), hashLittle(p, sizeofq-2, 13),
            hashLittle(p, sizeofq-3, 13), hashLittle(p, sizeofq-4, 13),
            hashLittle(p, sizeofq-5, 13), hashLittle(p, sizeofq-6, 13),
            hashLittle(p, sizeofq-7, 13), hashLittle(p, sizeofq-8, 13),
            hashLittle(p, sizeofq-9, 13), hashLittle(p, sizeofq-10, 13),
            hashLittle(p, sizeofq-11, 13), hashLittle(p, sizeofq-12, 13));
            printf("\n");

            /* check that hashlittle2 and hashlittle produce the same results */
            i=47; j=0;
            hashLittle(cast(void*)(q.ptr), sizeofq, &i, &j);
            if (hashLittle(cast(void*)(q.ptr), sizeofq, 47) != i)
                printf("hashLittle(4 params) and hashlittle(3 params) mismatch\n");

            /* check that hashword2 and hashword produce the same results */
            len = 0xdeadbeef;
            i=47, j=0;
            hashWord(&len, 1, &i, &j);
            if (hashWord(&len, 1, 47) != i)
                printf("hashWord(4 params) and hashWord(3 params) mismatch %x %x\n",
                i, hashWord(&len, 1, 47));

            /* check hashlittle doesn't read before or after the ends of the string */
            for (h=0, b=buf.ptr+1; h<8; ++h, ++b)
            {
                for (i=0; i<MaxLen; ++i)
                {
                    len = i;
                    for (j=0; j<i; ++j) *(b+j)=0;

                    /* these should all be equal */
                    refs = hashLittle(b, len, cast(uint)1);
                    *(b+i)=cast(ubyte)~0;
                    *(b-1)=cast(ubyte)~0;
                    x = hashLittle(b, len, cast(uint)1);
                    y = hashLittle(b, len, cast(uint)1);
                    if ((refs != x) || (refs != y))
                    {
                        printf("alignment error: %.8x %.8x %.8x %d %d\n",refs,x,y,
                                    h, i);
                    }
                }
            }
        }

        /* check for problems with nulls */
        void driver4()
        {
            ubyte[1] buf;
            uint h,i;
            uint[HashState] state;


            buf[0] = ~cast(ubyte)0;
            for (i=0; i<HashState; ++i) state[i] = 1;
            printf("These should all be different\n");
            for (i=0, h=0; i<8; ++i)
            {
                h = hashLittle(buf.ptr, 0, h);
                printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);
            }
        }

    // Test
    debug(hash)
    {
        driver2();  /* test that whole key is hashed thoroughly */
        driver3();  /* test that nothing but the key is hashed */
        driver4();  /* test hashing multiple buffers (all buffers are null) */
    }
}

/* --------------------------- 64 bit hash ----------------------------- */

ulong hashSize64(ulong n)
{
    return cast(ulong)1 << (n);
}

ulong hashMask64(ulong n)
{
    return hashSize64(n) - 1;
}

/**
 * mix three 64-bit values reversibly.
 * mix64() takes 48 machine instructions, but only 24 cycles on a superscalar
 * machine (like Intel's new MMX architecture).  It requires 4 64-bit
 * registers for 4::2 parallelism.
 * All 1-bit deltas, all 2-bit deltas, all deltas composed of top bits of
 * (a,b,c), and all deltas of bottom bits were tested.  All deltas were
 * tested both on random keys and on keys that were nearly all zero.
 * These deltas all cause every bit of c to change between 1/3 and 2/3
 * of the time (well, only 113/400 to 287/400 of the time for some
 * 2-bit delta).  These deltas all cause at least 80 bits to change
 * among (a,b,c) when the mix is run either forward or backward (yes it
 * is reversible).
 * This implies that a hash using mix64 has no funnels.  There may be
 * characteristics with 3-bit deltas or bigger, I didn't test for those.
*/

void mix64(ref ulong a, ref ulong b, ref ulong c)
{
    a -= b; a -= c; a ^= (c >> 43);
    b -= c; b -= a; b ^= (a << 9);
    c -= a; c -= b; c ^= (b >> 8);
    a -= b; a -= c; a ^= (c >> 38);
    b -= c; b -= a; b ^= ( a<< 23);
    c -= a; c -= b; c ^= ( b>> 5);
    a -= b; a -= c; a ^= (c >> 35);
    b -= c; b -= a; b ^= (a << 49);
    c -= a; c -= b; c ^= (b >> 11);
    a -= b; a -= c; a ^= (c >> 12);
    b -= c; b -= a; b ^= (a << 18);
    c -= a; c -= b; c ^= (b >> 22);
}

/**
 * hash a variable-length key into a 64-bit value
 * Returns a 64-bit value.  Every bit of the key affects every bit of
 * the return value.  No funnels.  Every 1-bit and 2-bit delta achieves
 * avalanche.  About 41+5len instructions.

 * The best hash table sizes are powers of 2.  There is no need to do
 * mod a prime (mod is sooo slow!).  If you need less than 64 bits,
 * use a bitmask.  For example, if you need only 10 bits, do
 * h = (h & hashMask64(10));
 * In which case, the hash table should have hashSize(10) elements.

 * If you are hashing n strings (ubyte**)k, do it like this:
 * for (i=0, h=0; i<n; ++i) h = hash64( k[i], len[i], h);

 * By Bob Jenkins, Jan 4 1997.  bob_jenkins@burtleburtle.net.  You may
 * use this code any way you wish, private, educational, or commercial,
 * but I would appreciate if you give me credit.

 * See: http://burtleburtle.net/bob/hash/evahash.html
 * Use for hash table lookup, or anything where one collision in 2^^64
 * is acceptable.  Do NOT use for cryptographic purposes.
 */

/**
 * Params: k -> the key (the unaligned variable-length array of bytes)
 *               len -> the length of the key, counting by bytes
 *               level -> can be any 8-byte value
 * Returns: a 64-bit value.
 */

ulong hash64(ubyte* k, ulong length, ulong level = 0)
{
    ulong a, b, c, len;
    // Set up the internal state
    len = length;
    a = b = level;  //the previous hash value
    c = 0x9e3779b97f4a7c13L;
    //handle most of the key
    while (len >= 24)
    {
        a += (k[0] + (cast(ulong)k[1] << 8)+(cast(ulong)k[2] << 16)+(cast(ulong)k[3] << 24)
                +(cast(ulong)k[4] << 32)+(cast(ulong)k[5] << 40)+(cast(ulong)k[6] << 48)+(cast(ulong)k[7] << 56));
        b += (k[8] + (cast(ulong)k[9] << 8)+(cast(ulong)k[10] << 16)+(cast(ulong)k[11] << 24)
                +(cast(ulong)k[12] << 32)+(cast(ulong)k[13] << 40)+(cast(ulong)k[14] << 48)+(cast(ulong)k[15] << 56));
        c += (k[16] + (cast(ulong)k[17] << 8)+(cast(ulong)k[18] << 16)+(cast(ulong)k[19] << 24)
                +(cast(ulong)k[20] << 32)+(cast(ulong)k[21] << 40)+(cast(ulong)k[22] << 48)+(cast(ulong)k[23] << 56));
        mix64(a,b,c);
        k += 24; len -= 24;
    }
    //handle the last 23 bytes
    c += length;
    switch(len)              /* all the case statements fall through */
    {
        case 23: c+=(cast(ulong)k[22] << 56);
        case 22: c+=(cast(ulong)k[21] << 48);
        case 21: c+=(cast(ulong)k[20] << 40);
        case 20: c+=(cast(ulong)k[19] << 32);
        case 19: c+=(cast(ulong)k[18] << 24);
        case 18: c+=(cast(ulong)k[17] << 16);
        case 17: c+=(cast(ulong)k[16] << 8);
        /* the first byte of c is reserved for the length */
        case 16: b+=(cast(ulong)k[15] << 56);
        case 15: b+=(cast(ulong)k[14] << 48);
        case 14: b+=(cast(ulong)k[13] << 40);
        case 13: b+=(cast(ulong)k[12] << 32);
        case 12: b+=(cast(ulong)k[11] << 24);
        case 11: b+=(cast(ulong)k[10] << 16);
        case 10: b+=(cast(ulong)k[9] << 8);
        case  9: b+=(cast(ulong)k[8]);
        case  8: a+=(cast(ulong)k[7] << 56);
        case  7: a+=(cast(ulong)k[6] << 48);
        case  6: a+=(cast(ulong)k[5] << 40);
        case  5: a+=(cast(ulong)k[4] << 32);
        case  4: a+=(cast(ulong)k[3] << 24);
        case  3: a+=(cast(ulong)k[2] << 16);
        case  2: a+=(cast(ulong)k[1]<<8);
        case  1: a+=(cast(ulong)k[0]);
        case 0: /*nothing left to add */
        default: break;
    }
    mix64(a,b,c);
    //report the result
    return c;
}

/**
 * This works on all machines, is identical to hash64(ubyte* k, ...) on little-endian
 * machines, and it is much faster than hash64(ubyte* k, ...), but it requires
 * -- that the key be an array of ulong's, and
 * -- that all your machines have the same endianness, and
 * -- that the length be the number of ulong's in the key
 */

ulong hash64(ulong* k, ulong length, ulong level = 0)
{
    ulong a, b, c, len;
    /* Set up the internal state */
    len = length;
    a = b = level;                         /* the previous hash value */
    c = 0x9e3779b97f4a7c13L;     /* the golden ratio; an arbitrary value */

    /* handle most of the key */
    while (len >= 3)
    {
        a += k[0];
        b += k[1];
        c += k[2];
        mix64(a,b,c);
        k += 3; len -= 3;
    }

    /* handle the last 2 ulong's */
    c += (length<<3);
    switch(len)              /* all the case statements fall through */
    {
        /* c is reserved for the length */
        case  2: b+=k[1];
        case  1: a+=k[0];
        case  0:  /* nothing left to add */
        default: break;
    }
    mix64(a,b,c);
    /* report the result */
    return c;
}

/**
 * This is identical to hash64(ubyte* k, ...) on little-endian machines, and it is much
 * faster than hash64(ubyte* k, ...), but a little slower than hash64(ulong*k, ...), and it requires
 * -- that all your machines be little-endian, for example all Intel x86
 *  chips or all VAXen.  It gives wrong results on big-endian machines.
 */

ulong hash64II(ubyte* k, ulong length, ulong level = 0)
{
    ulong a,b,c,len;

    /* Set up the internal state */
    len = length;
    a = b = level;                         /* the previous hash value */
    c = 0x9e3779b97f4a7c13L;     /* the golden ratio; an arbitrary value */

    /* handle most of the key */
    if ((cast(size_t)k) & 7)
    {
        while (len >= 24)
        {
            a += (k[0] + (cast(ulong)k[ 1] << 8)+(cast(ulong)k[2] << 16)+(cast(ulong)k[3] << 24)
                    +(cast(ulong)k[4] << 32)+(cast(ulong) k[5] << 40)+(cast(ulong)k[6] << 48)+(cast(ulong)k[7] << 56));
            b += (k[8] + (cast(ulong)k[9] << 8)+(cast(ulong)k[10] << 16)+(cast(ulong)k[11] << 24)
                    +(cast(ulong)k[12] << 32)+(cast(ulong)k[13] << 40)+(cast(ulong)k[14] << 48)+(cast(ulong)k[15] << 56));
            c += (k[16] + (cast(ulong)k[17] << 8)+(cast(ulong)k[18] << 16)+(cast(ulong)k[19] << 24)
                    +(cast(ulong)k[20] << 32)+(cast(ulong)k[21] << 40)+(cast(ulong)k[22] << 48)+(cast(ulong)k[23] << 56));
            mix64(a,b,c);
            k += 24; len -= 24;
        }
    }
    else
    {
        while (len >= 24)    /* aligned */
        {
            a += *cast(ulong*)(k+0);
            b += *cast(ulong*)(k+8);
            c += *cast(ulong*)(k+16);
            mix64(a,b,c);
            k += 24; len -= 24;
        }
    }

    /* handle the last 23 bytes */
    c += length;
    switch(len)              /* all the case statements fall through */
    {
        case 23: c+=(cast(ulong)k[22] << 56);
        case 22: c+=(cast(ulong)k[21] << 48);
        case 21: c+=(cast(ulong)k[20] << 40);
        case 20: c+=(cast(ulong)k[19] << 32);
        case 19: c+=(cast(ulong)k[18] << 24);
        case 18: c+=(cast(ulong)k[17] << 16);
        case 17: c+=(cast(ulong)k[16] << 8);
        /* the first byte of c is reserved for the length */
        case 16: b+=(cast(ulong)k[15] << 56);
        case 15: b+=(cast(ulong)k[14] << 48);
        case 14: b+=(cast(ulong)k[13] << 40);
        case 13: b+=(cast(ulong)k[12] << 32);
        case 12: b+=(cast(ulong)k[11] << 24);
        case 11: b+=(cast(ulong)k[10] << 16);
        case 10: b+=(cast(ulong)k[9] << 8);
        case  9: b+=(cast(ulong)k[8]);
        case  8: a+=(cast(ulong)k[7] << 56);
        case  7: a+=(cast(ulong)k[6] << 48);
        case  6: a+=(cast(ulong)k[5] << 40);
        case  5: a+=(cast(ulong)k[4] << 32);
        case  4: a+=(cast(ulong)k[3] << 24);
        case  3: a+=(cast(ulong)k[2] << 16);
        case  2: a+=(cast(ulong)k[1] << 8);
        case  1: a+=(cast(ulong)k[0]);
        case 0: /* nothing left to add */
        default: break;
    }
    mix64(a,b,c);
    /* report the result */
    return c;
}


unittest
{
    const ulong HASHSTATE = 1L;
    const HASHLEN = 1L;
    const MAXPAIR = 80L;
    const MAXLEN = 5L;

    /* check that every input bit changes every output bit half the time */
    void driver2()
    {
        ubyte[MAXLEN+1] qa;
        ubyte[MAXLEN+2] qb;
        ubyte* a = &qa[0];
        ubyte* b = &qb[1];
        ulong[HASHSTATE] c, d;
        uint i, j=0, k, l, m, z;
        ulong[HASHSTATE] e, f, g, h;
        ulong[HASHSTATE] x, y;
        ulong hlen;

        printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
        for (hlen=0; hlen < MAXLEN; ++hlen)
        {
            z=0;
            for (i=0; i<hlen; ++i)  /*----------------------- for each byte, */
            {
                for (j=0; j<8; ++j)   /*------------------------ for each bit, */
                {
                    for (m=0; m<8; ++m) /*-------- for serveral possible levels, */
                    {
                        for (l=0; l<HASHSTATE; ++l)
                        {
                            e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~(cast(ulong)0);
                        }

                        /*---- check that every input bit affects every output bit */
                        for (k=0; k<MAXPAIR; k+=2)
                        {
                            ulong finished=1;
                            /* keys have one bit different */
                            for (l=0; l<hlen+1; ++l) {a[l] = b[l] = cast(ubyte)0;}
                            /* have a and b be two keys differing in only one bit */
                            a[i] ^= (k<<j);
                            a[i] ^= (k>>(8-j));
                            c[0] = hash64(a, hlen, m);
                            b[i] ^= ((k+1)<<j);
                            b[i] ^= ((k+1)>>(8-j));
                            d[0] = hash64(b, hlen, m);
                            /* check every bit is 1, 0, set, and not set at least once */
                            for (l=0; l<HASHSTATE; ++l)
                            {
                                e[l] &= (c[l]^d[l]);
                                f[l] &= ~(c[l]^d[l]);
                                g[l] &= c[l];
                                h[l] &= ~c[l];
                                x[l] &= d[l];
                                y[l] &= ~d[l];
                                if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
                            }
                            if (finished) break;
                        }
                        if (k>z) z=k;
                        if (k==MAXPAIR)
                        {
                            printf("Some bit didn't change: ");
                            printf("%.8lx %.8lx %.8lx %.8lx %.8lx %.8lx  ",
                                    e[0],f[0],g[0],h[0],x[0],y[0]);
                            printf("i %ld j %ld m %ld len %ld\n",
                                    cast(uint)i, cast(uint)j, cast(uint)m, cast(uint)hlen);
                        }
                        if (z==MAXPAIR) goto done;
                    }
                }
            }
            done:
            if (z < MAXPAIR)
            {
                printf("Mix success  %2ld bytes  %2ld levels  ",cast(uint)i,cast(uint)m);
                printf("required  %ld  trials\n",cast(uint)(z/2));
                assert(true);
            }
        }
        printf("\n");
    }

    /* Check for reading beyond the end of the buffer and alignment problems */
    void driver3()
    {
        ubyte[MAXLEN+20] buf;
        ubyte* b;
        ulong len;
        string q = "This is the time for all good men to come to the aid of their country" ~ "\0";
        string qq = "xThis is the time for all good men to come to the aid of their country" ~ "\0";
        string qqq = "xxThis is the time for all good men to come to the aid of their country" ~ "\0";
        string qqqq = "xxxThis is the time for all good men to come to the aid of their country" ~ "\0";
        string o = "xxxxThis is the time for all good men to come to the aid of their country" ~ "\0";
        string oo = "xxxxxThis is the time for all good men to come to the aid of their country" ~ "\0";
        string ooo = "xxxxxxThis is the time for all good men to come to the aid of their country" ~ "\0";
        string oooo = "xxxxxxxThis is the time for all good men to come to the aid of their country" ~ "\0";
        ulong h,i,j,refs,x,y;

        printf("Endianness.  These should all be the same:\n");
        size_t sizeofq = q.length;
        h = hash64(cast(ubyte*)q.ptr+0, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)qq.ptr+1, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)qqq.ptr+2, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)qqqq.ptr+3, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)o.ptr+4, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)oo.ptr+5, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)ooo.ptr+6, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        h = hash64(cast(ubyte*)oooo.ptr+7, cast(ulong)(sizeofq-1), cast(ulong)0);
        printf("%.8lx%.8lx\n", cast(uint)h, cast(uint)(h >> 32));
        printf("\n");
        for (h=0, b=buf.ptr+1; h<8; ++h, ++b)
        {
            for (i=0; i<MAXLEN; ++i)
            {
                len = i;
                for (j=0; j<i; ++j) *(b+j)=0;

                /* these should all be equal */
                refs = hash64(b, len, cast(ulong)1);
                *(b+i)=cast(ubyte)~0;
                *(b-1)=cast(ubyte)~0;
                x = hash64(b, len, cast(ulong)1);
                y = hash64(b, len, cast(ulong)1);
                if ((refs != x) || (refs != y))
                {
                    printf("alignment error: %.8lx %.8lx %.8lx %ld %ld\n",refs,x,y,h,i);
                }
            }
        }
    }

    /* check for problems with nulls */
    void driver4()
    {
        ubyte[1] buf;
        uint i;
        ulong h;
        ulong[HASHSTATE] state;


        buf[0] = ~cast(ubyte)0;
        for (i=0; i<HASHSTATE; ++i) state[i] = 1;
        printf("These should all be different\n");
        for (i=0, h=0; i<8; ++i)
        {
            h = hash64(buf.ptr, cast(ulong)0, h);
            printf("%2ld  0-byte strings, hash is  %.8lx%.8lx\n", cast(uint)i,
                        cast(uint)h, cast(uint)(h >> 32));
        }
    }
    debug(hash)
    {
        driver2();   /* test that whole key is hashed thoroughly */
        driver3();   /* test that nothing but the key is hashed */
        driver4();   /* test hashing multiple buffers (all buffers are null) */
    }
}